#ifndef __MAP_HPP__
#define __MAP_HPP__

#include <cstring>
#include "globaldef.hpp"
#include "Coord.hpp"
#include <queue>
#include <deque>
#include <list>
#include <tuple>
#include <utility>
#include <vector>

#define _MT(x, y, mark) std::make_tuple(x, y, mark)

/**
 * @brief 地图
 */
class Map {
private:
    struct TimeBlock { // 时空障碍物
        Coord end; // 指定时刻下时空障碍物的坐标
        direction_t dir; // 时空障碍物抵达该坐标前的方向
        TimeBlock();
        TimeBlock(const Coord &end, direction_t dir): 
            end(end), dir(dir) {
            
        }
        bool operator==(const TimeBlock &other) const {
            return end == other.end && dir == other.dir;
        }
        /**
         * @brief 与时空障碍物相同时刻下以指定方向到达指定坐标是否会发生碰撞
         * @param end 
         * @param dir 
         * @return true 
         * @return false 
         */
        bool willCrash(Coord end, direction_t dir) const {
            if (this->end == end) { // 移动的终点和时空障碍物相同，会碰撞
                return true;
            }
            Coord thisStart = this->end;
            thisStart.moveCoord(this->dir, true);
            Coord targetStart = end;
            targetStart.moveCoord(dir, true);
            if (thisStart == targetStart) { // 移动的起点和时空障碍物相同，会碰撞
                return true;
            }
            if (thisStart == end && this->end == targetStart) { // 移动的起点与终点恰好和时空障碍物相反，会碰撞
                return true;
            }
            return false;
        }
    };

public:
    typedef std::vector<std::vector<unsigned short>> distable_t; // 距离表
    char buff[MAP_X_MAX][MAP_Y_MAX]; // 地图
    Coord robotsInit[ROBOT_NUM]; // 机器人初始位置
    std::vector<distable_t> berthDistance = std::vector<distable_t>(BERTH_NUM, distable_t(MAP_X_MAX, std::vector<unsigned short>(MAP_Y_MAX, DISTANCE_INF))); // 泊位距离表
    std::deque<std::list<TimeBlock>> timeBlocks; // 时空障碍物表
    char nearestBerth[MAP_X_MAX][MAP_Y_MAX]; //
    int berthArea[BERTH_NUM]; // 辖区面积
    char id = 3; // 地图编号

public:
    /**
     * @brief 构造函数
     */
    Map() {
        std::memset(buff, 0, sizeof(buff));
        std::memset(nearestBerth, 0XFF, sizeof(nearestBerth));
        std::memset(berthArea, 0, sizeof(berthArea));
    }
    /**
     * @brief 判断地图ID
     */
    void init() {
        static const std::vector<std::vector<std::tuple<int, int, char>>> featureTable = { // 地图特征表
        /* 地图1 */ {_MT( 14, 88,'A'),_MT( 29, 88,'A'),_MT( 58, 90,'A'),_MT( 59, 21,'A'),_MT( 59,140,'A'),_MT( 82, 86,'A'),_MT(102, 89,'A'),_MT(157, 47,'A'),_MT(177, 69,'A'),_MT(195, 72,'A'),},
        /* 地图2 */ {_MT( 36,173,'A'),_MT( 55, 89,'A'),_MT(108, 74,'A'),_MT(108,127,'A'),_MT(130, 85,'A'),_MT(130,141,'A'),_MT(163, 62,'A'),_MT(165,128,'A'),_MT(181, 28,'A'),_MT(193,124,'A'),},
        /* 地图3 */ {_MT( 30, 30,'A'),_MT( 30, 70,'A'),_MT( 30,130,'A'),_MT( 30,170,'A'),_MT( 69, 30,'A'),_MT( 69,170,'A'),_MT(130, 30,'A'),_MT(130,170,'A'),_MT(169,130,'A'),_MT(169,170,'A'),},
        /* 地图4 */ {_MT(  8, 75,'A'),_MT(  8,125,'A'),_MT( 25, 39,'A'),_MT( 25,143,'A'),_MT( 32,168,'A'),_MT( 37, 40,'A'),_MT(164, 66,'A'),_MT(165,138,'A'),_MT(172, 40,'A'),_MT(175,170,'A'),},
        /* 地图5 */ {_MT( 24, 78,'A'),_MT( 24,118,'A'),_MT( 47,100,'A'),_MT( 67, 78,'A'),_MT( 67,118,'A'),_MT(131, 78,'A'),_MT(131,118,'A'),_MT(154,100,'A'),_MT(174, 78,'A'),_MT(174,118,'A'),},
        /* 地图6 */ {_MT( 25, 79,'A'),_MT( 25,119,'A'),_MT( 47,153,'A'),_MT( 69, 79,'A'),_MT( 69,119,'A'),_MT(130, 79,'A'),_MT(130,119,'A'),_MT(152, 44,'A'),_MT(174, 79,'A'),_MT(174,119,'A'),},
        /* 地图7 */ {_MT( 26, 26,'A'),_MT( 29, 63,'A'),_MT( 85,149,'A'),_MT( 90, 32,'A'),_MT(116, 80,'A'),_MT(118, 29,'A'),_MT(130,143,'A'),_MT(136, 72,'A'),_MT(167,122,'A'),_MT(167,173,'A'),},
        /* 地图8 */ {_MT( 70,193,'A'),_MT( 72,193,'A'),_MT( 74,193,'A'),_MT( 77,193,'A'),_MT(106,193,'A'),_MT(109,193,'A'),_MT(112,193,'A'),_MT(115,193,'A'),_MT(118,193,'A'),_MT(121,193,'A'),}
        };
        // 使用排除法判断地图
        std::vector<bool> selected(featureTable.size(), true); // 还需要判断的地图
        for (int featureIndex = 0; featureIndex < featureTable[0].size(); ++featureIndex) {
            for (int mapID = 0; mapID < featureTable.size(); ++mapID) {
                if (selected[mapID]) {
                    auto const &feature = featureTable[mapID][featureIndex];
                    if (get(std::get<0>(feature), std::get<1>(feature)) != std::get<2>(feature)) {
                        selected[mapID] = false;
                    }
                }
            }
        }
        // 查询选中的地图
        int result = -1;
        int cnt = 0;
        for (int mapID = 0; mapID < featureTable.size(); ++mapID) {
            if (selected[mapID]) {
                result = mapID + 1;
                ++cnt;
            }
        }
        if (cnt == 1) {
            id = result;
            LOG("地图[%d]\n", id)
        } else {
            LOG("未找到当前地图！\n")
        }
        LOG("=======================================\n");
    }
    /**
     * @brief 刷新地图
     */
    void refresh() {
        if (!timeBlocks.empty()) {
            timeBlocks.pop_front();
        }
    }
    /**
     * @brief 设置永久障碍物
     * @param coord 
     */
    void addBlock(const Coord &coord) {
        char c = get(coord);
        set(coord, c > 0 ? -c : c); // char只用了低7位存ASCII码，符号位置1即可避免冲突
    }
    /**
     * @brief 删除永久障碍物
     * @param coord 
     */
    void deleteBlock(const Coord &coord) {
        char c = get(coord);
        set(coord, c < 0 ? -c : c);
    }
    /**
     * @brief 查询是否存在永久障碍物
     * @param coord 
     * @return true 
     * @return false 
     */
    bool isBlock(const Coord &coord) {
        return get(coord) < 0;
    }
    /**
     * @brief 添加时空障碍物
     * @param coord 指定时刻下时空障碍物的坐标
     * @param dir 时空障碍物抵达指定坐标前的方向
     * @param time 从此刻开始计时，时空障碍物抵达指定位置所用的帧数
     * @brief 不考虑重复添加，添加两次的话，删除也需要两次
     */
    void addTimeBlock(const Coord& coord, direction_t dir = INPLACE, size_t time = 1) {
        if (time == 0 || time >= TIME_FRAME_MAX) {
            LOG("addTimeBlock: [time == %lu], out of time range!\n", time)
            return;
        }
        while(timeBlocks.size() < time) {
            timeBlocks.push_back(std::list<TimeBlock>());
        }
        timeBlocks[time - 1].push_back(TimeBlock(coord, dir));
    }
    /**
     * @brief 删除时空障碍物
     * @param time 从此刻开始计时，时空障碍物抵达指定位置所用的帧数
     * @param coord 指定时刻下时空障碍物的坐标
     * @param dir 时空障碍物抵达指定坐标前的方向
     */
    void deleteTimeBlock(size_t time, const Coord& coord, direction_t dir = INPLACE) {
        if (time == 0 || time > timeBlocks.size()) {
            LOG("deleteTimeBlock: [time == %lu], out of time range!\n", time)
            return;
        }
        TimeBlock target(coord, dir);
        auto &frame = timeBlocks[time - 1];
        for (auto it = frame.begin(); it != frame.end(); ++it) {
            if (target == *it) {
                frame.erase(it);
                return;
            }
        }
    }
    /**
     * @brief 查询是否会与时空障碍物发生碰撞
     * @param time 从此刻开始计时，时空障碍物抵达指定位置所用的帧数
     * @param coord 指定时刻下时空障碍物的坐标
     * @param dir 时空障碍物抵达指定坐标前的方向
     * @param crashedDir 用于获取时空障碍物的方向，无时空障碍物时，不改变该值
     * @return true 
     * @return false 
     */
    bool willCrashTimeBlock(size_t time, const Coord& coord, direction_t dir = INPLACE, direction_t *crashedDir = nullptr) const {
        #ifdef USE_LOG
        if (time == 0 || time >= TIME_FRAME_MAX) {
            LOG("willCrashTimeBlock: [time == %lu], out of time range!\n", time)
            return false;
        }
        if (time > timeBlocks.size()) {
            return false;
        }
        #else
        if (time == 0 || time > timeBlocks.size()) {
            return false;
        }
        #endif
        auto &frame = timeBlocks[time - 1];
        for (auto it = frame.begin(); it != frame.end(); ++it) {
            if (it->willCrash(coord, dir)) {
                if (crashedDir) {
                    *crashedDir = it->dir;
                }
                return true;
            }
        }
        return false;
    }
    /**
     * @brief 设置某点地图符号
     * @param x
     * @param y
     * @param mark
     */
    void set(int x, int y, char mark) {
        if (mark == MARK_ROBOT) {
            static int robotID = 0;
            robotsInit[robotID].x = x;
            robotsInit[robotID].y = y;
            ++robotID;
        }
        buff[x][y] = mark;
    }
    /**
     * @brief 设置某点地图符号
     * @param coord
     * @param mark
     */
    void set(const Coord &coord, char mark) {
        set(coord.x, coord.y, mark);
    }
    /**
     * @brief 获取地图某点信息
     * @param x
     * @param y
     * @return char
     */
    char get(int x, int y) const {
        return buff[x][y];
    }
    /**
     * @brief 获取地图某点信息
     * @param coord
     * @return char
     */
    char get(const Coord &coord) const {
        return get(coord.x, coord.y);
    }
    /**
     * @brief 是否为陆地上可以走的路
     * @param coord 
     * @param includeBerth 是否包含泊位 
     * @return true 
     * @return false 
     */
    bool isLandPath(const Coord &coord, bool includeBerth = true) const {
        char mark = get(coord);
        return mark > 0 && mark != MARK_OBSTACLE && mark != MARK_OCEAN && (includeBerth || !isBerth(coord));
    }
    /**
     * @brief 某点周围障碍物数量（非LandPath即视作障碍物）
     * @param coord 
     * @param berthIsObstacles 泊位是否算作障碍物 
     * @return int 
     */
    int aroundObstacles(const Coord &coord,  bool berthIsObstacles = false) {
        int ret = 0;
        for (int i = 1; i <= 4; ++i) {
            direction_t dir = static_cast<direction_t>(i);
            Coord newCoord(coord, dir);
            if (newCoord.isInRect(0, 0, MAP_X_MAX, MAP_Y_MAX) && this->isLandPath(newCoord, berthIsObstacles)) {
                ++ret;
            }
        }
        return ret;
    }
    /**
     * @brief 是否为泊位
     * @param coord 
     * @return true 
     * @return false 
     */
    bool isBerth(const Coord &coord) const {
        return get(coord) == MARK_BERTH;
    }
    /**
     * @brief 设置到指定泊位的距离
     * @param berthID
     * @param coord
     * @param dis
     */
    void setBerthDistance(int berthID, const Coord &coord, unsigned short dis) {
        berthDistance[berthID][coord.x][coord.y] = dis;
    }
    /**
     * @brief 初始化泊位距离表
     * @param berthID
     * @param coord
     */
    void initBerthDistance(int berthID, const Coord &coord) {
        bool visited[MAP_X_MAX][MAP_Y_MAX];
        memset(visited, 0, sizeof(visited));
        std::queue<Coord> originQueue, queue;

        // 先遍历起点队列，将港口周围第一圈的点全部入队
        originQueue.push(coord);
        this->setBerthDistance(berthID, coord, 0); // 起点距离为0
        while (!originQueue.empty()) {
            auto it = originQueue.front();
            originQueue.pop();
            if (!visited[it.x][it.y]) {
                visited[it.x][it.y] = true;
                for (int i = 1; i <= 4; ++i) {
                    Coord newCoord(it, static_cast<direction_t>(i));
                    if (newCoord.isInRect(0, 0, MAP_X_MAX, MAP_Y_MAX) && !visited[newCoord.x][newCoord.y]) {
                        if (this->isBerth(newCoord)) {
                            originQueue.push(newCoord);
                            this->setBerthDistance(berthID, newCoord, 0); // 港口点距离为0
                        } else if (this->isLandPath(newCoord)) {
                            queue.push(newCoord);
                        }
                    }
                }
            }
        }

        // 逐圈遍历坐标，以空结点作为分层标志
        unsigned short distance = 1;
        Coord nullCoord(-1, -1);
        queue.push(nullCoord);
        while (!queue.empty()) {
            auto it = queue.front();
            queue.pop();
            if (it == nullCoord) {
                ++distance;
                if (!queue.empty() && queue.front() != nullCoord) {
                    queue.push(nullCoord);
                }
            } else if (!visited[it.x][it.y]){
                visited[it.x][it.y] = true;
                this->setBerthDistance(berthID, it, distance);
                for (int i = 1; i <= 4; ++i) {
                    Coord newCoord(it, static_cast<direction_t>(i));
                    if (newCoord.isInRect(0, 0, MAP_X_MAX, MAP_Y_MAX) && !visited[newCoord.x][newCoord.y]) {
                        if (this->isLandPath(newCoord)) {
                            queue.push(newCoord);
                        }
                    }
                }
            }
        }
    }
    /**
     * @brief 获取到指定泊位的距离
     * @param berthID
     * @param x
     * @param y
     * @return int
     */
    int getBerthDistance(int berthID, int x, int y) const {
        return static_cast<int>(berthDistance[berthID][x][y]);
    }
    /**
     * @brief 获取到指定泊位的距离
     * @param berthID
     * @param coord
     * @return int
     */
    int getBerthDistance(int berthID, const Coord &coord) const {
        return getBerthDistance(berthID, coord.x, coord.y);
    }
    /**
     * @brief 初始化最近泊位表
     * @return int 
     */
    void initNearestBerthTable() {
        for (int x = 0; x < MAP_X_MAX; ++x) {
            for (int y = 0; y < MAP_Y_MAX; ++y) {
                int min = DISTANCE_INF;
                int minID = INVALID_BERTH_ID;
                for (int id = 0; id < BERTH_NUM; ++id) {
                    int dis = getBerthDistance(id, x, y);
                    if (dis < min) {
                        min = dis;
                        minID = id;
                    } else if (dis != DISTANCE_INF && dis == min) { // 距离相等，优先取面积小的
                        minID = berthArea[id] < berthArea[minID] ? id : minID;
                    }
                }
                nearestBerth[x][y] = minID;
                if (minID >= 0 && minID < BERTH_NUM) {
                    ++berthArea[minID];
                }
            }
        }
    }
    /**
     * @brief 获取港口辖区面积
     * @param berthID 
     * @return int 
     */
    int getBerthAreaS(int berthID) const {
        if (berthID >= 0 && berthID < BERTH_NUM) {
            return berthArea[berthID];
        }
        return 0;
    }
    /**
     * @brief 获取到指定坐标最近的泊位
     * @param coord 
     * @return int 
     */
    int getNearestBerth(const Coord &coord) const {
        return nearestBerth[coord.x][coord.y];
    }
    /**
     * @brief 判断指定点是否能到达任意泊位
     * @param coord 
     * @return true 
     * @return false 
     */
    bool isBerthArrival(const Coord &coord) const {
        return getNearestBerth(coord) != INVALID_BERTH_ID;
    }
    /**
     * @brief 获取指定坐标所有可达的泊位
     * @param coord 
     * @return std::vector<int> 
     */
    std::vector<int> getArrivalBerths(const Coord &coord) const {
        std::vector<int> ret;
        for (int i = 0; i < BERTH_NUM; ++i) {
            if (berthDistance[i][coord.x][coord.y] != DISTANCE_INF) {
                ret.push_back(i);
            }
        }
        return ret;
    }
    /**
     * @brief 计算距离表
     * @param point 
     * @return distable_t 
     */
    distable_t *getDistanceTable(const Coord &point) {
        distable_t *ret = new distable_t(MAP_X_MAX, std::vector<unsigned short>(MAP_Y_MAX, DISTANCE_INF));
        bool visited[MAP_X_MAX][MAP_Y_MAX];
        memset(visited, 0, sizeof(visited));
        std::queue<Coord> queue;
        queue.push(point);
        // 逐圈遍历坐标，以空结点作为分层标志
        unsigned short distance = 0;
        Coord nullCoord(-1, -1);
        queue.push(nullCoord);
        while (!queue.empty()) {
            auto it = queue.front();
            queue.pop();
            if (it == nullCoord) {
                ++distance;
                if (!queue.empty() && queue.front() != nullCoord) {
                    queue.push(nullCoord);
                }
            } else if (!visited[it.x][it.y]){
                visited[it.x][it.y] = true;
                (*ret)[it.x][it.y] = distance;
                for (int i = 1; i <= 4; ++i) {
                    Coord newCoord(it, static_cast<direction_t>(i));
                    if (newCoord.isInRect(0, 0, MAP_X_MAX, MAP_Y_MAX) && !visited[newCoord.x][newCoord.y]) {
                        if (this->isLandPath(newCoord)) {
                            queue.push(newCoord);
                        }
                    }
                }
            }
        }
        return ret;
    }
};

#endif // __MAP_HPP__